package com.changanw.code34;

import java.util.Arrays;

/**
 * @author changanw
 * @description 二分法查找数组中，在排序数组中查找元素的第一个和最后一个位置
 * @date 2023/7/31 20:45
 */
public class Code34 {
  public int[] searchRange(int[] nums, int target) {
    int leftIdx = binarySearch(nums, target, true);
    int rightIdx = binarySearch(nums, target, false) - 1;
    if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
      return new int[]{leftIdx, rightIdx};
    }
    return new int[]{-1, -1};

    /*int left = 0;
    int right = nums.length -1;
    int first = -1;
    int last = -1;
    while (left < right){
      int mid = left + (right - left)/2;
      if (nums[mid] == target){
        first = mid;
        right = mid -1;
      }else if (nums[mid] > target){
        right = mid - 1;
      }else {
        left = mid + 1;
      }
    }
    //第二个目标位置
    left = 0;
    right = nums.length - 1;
    while (left < right){
      int mid = left + (right - left)/2;
      if (nums[mid] == target){
        last = mid;
        left = mid  + 1;
      }else if (nums[mid] > target){
        right = mid - 1;
      }else {
        left = mid + 1;
      }
    }
    return new int[]{last,first};*/


   /* int upper = upperBound(nums,target);
    int low = lowerBound(nums,target);
    if (upper < low){
      return new int[]{-1,-1};
    }

    return new int[]{low,upper};*/
  }
  public int binarySearch(int[] nums, int target, boolean lower) {
    int left = 0, right = nums.length - 1, ans = nums.length;
    while (left <= right) {
      int mid = (left + right) / 2;
      if (nums[mid] > target || (lower && nums[mid] >= target)) {
        right = mid - 1;
        ans = mid;
      } else {
        left = mid + 1;
      }
    }
    return ans;
  }

  //下边界
  public int lowerBound(int[] nums, int target){
    int l = 0;
    int r = nums.length -1;
    while (l <= r){
      int mid = l + (r-l)/2;
      if (target <= nums[mid]){
        r = mid -1;
      }else if (target > nums[mid]){
        l = mid + 1;
      }
    }
    return l;
  }
  //上边界
  public int upperBound(int[] nums, int target){
    int l = 0;
    int r = nums.length -1;
    while (l <= r){
      int mid = l + (r-l)/2;
      if (target >= nums[mid]){
        l = mid + 1;
      }else if (target < nums[mid]){
        r = mid -1;
      }
    }
    return r;
  }

  public static void main(String[] args) {
    Code34 code34 = new Code34();
    int[] nums = {7,7,7,7,7,7};
    int target = 7;
    int[] ints = code34.searchRange(nums,target);
    System.out.println(Arrays.toString(ints));
  }
}
